class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n,1);//f(n)=f(n-1)+nums(n-1)
        vector<int> g(n,1);//g(n)=g(n+1)+nums(n+1)

        for(int i=1;i<n;++i)
        {
            f[i]=f[i-1]*nums[i-1];
        }

        for(int i=n-2;i>=0;--i)
        {
            g[i]=g[i+1]*nums[i+1];
        }
        vector<int> ret(n);
        for(int i=0;i<n;++i)
        {
            ret[i]=f[i]*g[i];
            
        }
        return ret;
    }
};
